package leetcode.f1t100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给出数组, 目标, 返回任意个数字相加等于目标值的集合, 数字不可重复使用
 * https://leetcode.com/problems/combination-sum-ii/
 *
 * @Author lichongxiao
 * @Date 2022/10/12 17:34
 */
public class Q40_CombinationSumII {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> answers = new ArrayList<>();
        Arrays.sort(candidates);
        process(candidates, 0, target, new ArrayList<>(), answers);
        return answers;
    }

    private void process(int[] candidates, int i, int target, ArrayList<Integer> tempList, List<List<Integer>> answers) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            answers.add(new ArrayList<>(tempList));
            return;
        }
        for (int j = i; j < candidates.length; j++) {
            if(j > i && candidates[j-1] == candidates[j]){
                continue;
            }
            tempList.add(candidates[j]);
            process(candidates, j + 1, target - candidates[j], tempList, answers);
            tempList.remove(tempList.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> answers = new Q40_CombinationSumII().combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8);
        for(List<Integer> answer : answers){
            for(Integer num : answer){
                System.out.print(num + "_");
            }
            System.out.println();
        }

    }
}
